package class26;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class Parentheses {

    public static boolean isValid(String str) {
        if (str == null || str.length() == 0) {
            return false;
        }
        char[] c = str.toCharArray();
        int n = c.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == '(') {
                count++;
            } else {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }

    public static int needParentheses(String str) {
        char[] c = str.toCharArray();
        int n = c.length;
        int count = 0;
        int need = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == '(') {
                count++;
            } else {
                count--;
            }
            if (count == -1) {
                need++;
                count = 0;
            }
        }
        return need + count;
    }

    public static int needParentheses2(String str) {
        char[] c = str.toCharArray();
        int n = c.length;
        int count = 0;
        int need = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == '(') {
                count++;
            } else {
                if (count == 0) {
                    need++;
                } else {
                    count--;
                }
            }
        }
        return need + count;
    }

    public static int maxParenthesesLen(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] c = str.toCharArray();
        int n = c.length;
        int[] dp = new int[n];
        dp[0] = 0;
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (c[i] == ')') {
                if (i - dp[i - 1] - 1 >= 0) {
                    dp[i] = c[i - dp[i - 1] - 1] == '(' ? dp[i - 1] + 2 : 0;
                }
                if (i - dp[i - 1] - 2 >= 0) {
                    dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static int deep(String str) {
        char[] c = str.toCharArray();
        int max = 0;
        int count = 0;
        for (int i = 0; i < c.length; i++) {
            count = c[i] == '(' ? count + 1 : count - 1;
            max = Math.max(max, count);
        }
        return max;
    }
}
